# 把二叉搜索树转换为累加树: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

        
class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        """
            这道题有点求前缀和的感觉， 但是 按照中序遍历是 升序的序列， 这里需要求大于 该元素值得和
            所以 反着求, 右根左， 进行累加
        """
        pre = None
        def reverseInorder(node):
            nonlocal pre
            if not node: return

            reverseInorder(node.right)
            if pre:
                node.val = node.val + pre.val
            pre = node
            reverseInorder(node.left)

        reverseInorder(root)

        return root
